package com.zhj.structure.tree.utils;

/**
 * @PackageName:com.zhj.structure.tree.utils
 * @ClassName:BinarySortTree
 * @auter: 朱慧杰
 * @date:2020/8/12 0012 9:44
 **/
public class BinarySortTree {
    // 二叉排序树

    TreeNode root;

    // 向二叉排序树添加节点
    public void add(TreeNode node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    public void deleteNode(int value) {
        if (root == null) {
            System.out.println("这是一棵空树，没有可以删除的节点！");
            return;
        } else {
            TreeNode target = search(value);
            if (target == null) {
                System.out.println("抱歉没有找到您要删除的节点 " + value + " 请确定后再操作！");
                return;
            }
            // 找到父节点
            TreeNode parent =  searchParent(value);
            // 要删除的节点是叶子节点
            if (target.leftNode == null && target.rightNode == null) {
                if (parent.leftNode.getValue() == value) {
                    parent.leftNode = null;
                } else {
                    parent.rightNode = null;
                }
            } else if (target.leftNode != null && target.rightNode !=null) {
                // 删除右子树最小的节点，并获取值
                int min = deleteRightMin(target.rightNode);
                target.setValue(min);
                // 或者是删除左子树最大的节点，并获取值
            } else { // 有一个节点
                if (target.leftNode != null) {
                    if (parent.leftNode.getValue() == value) {
                        parent.leftNode = target.leftNode;
                    } else {
                        parent.rightNode = target.leftNode;
                    }
                } else {
                    if (parent.leftNode.getValue() == value) {
                        parent.leftNode = target.rightNode;
                    } else {
                        parent.rightNode = target.rightNode;
                    }
                }
            }
        }
    }

    public int deleteRightMin(TreeNode node) {
        TreeNode target = node;
        while (target.leftNode != null) {
            target = target.leftNode;
        }
        deleteNode(target.getValue());
        return target.getValue();
    }

    public int deleteLeftMax(TreeNode node) {
        TreeNode target = node;
        while (target.rightNode != null) {
            target = target.rightNode;
        }
        deleteNode(target.getValue());
        return target.getValue();
    }

    public TreeNode searchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchParent(value);
        }
    }

    public void frontShow() {
        System.out.println("前序遍历：");
        if (root!=null) {
            root.frontShow();
        } else {
            System.out.println("空的树");
        }
        System.out.println();
    }

    public void midShow() {
        System.out.println("中序遍历：");
        if (root!=null) {
            root.midShow();
        } else {
            System.out.println("空的树");
        }
        System.out.println();
    }

    public TreeNode search(int value) {
        if (root == null) {
            System.out.println("抱歉，没有搜索到 " + value);
            return null;
        }
        TreeNode temp = root.search(value);
        if (temp == null) {
            System.out.println("抱歉，没有搜索到 " + value);
            return null;
        } else {
            System.out.println("恭喜您，你要查找的 " + value + " 找到了 " + temp);
            return temp;
        }
    }
}
